package
{
	public class QuickSortClass
	{
		/**
		 *取代冒泡排序的优化算法 
		 */		
		public function QuickSortClass()
		{
			
		}
		private function DivisionIncrease(list:Array, left:int , right:int):int
		{
			//首先挑选一个基准元素
			var baseNum:int = list[left];
			
			while (left < right)
			{
				//从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
				while (left < right && list[right] >= baseNum)
					right = right - 1;
				
				//最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
				list[left] = list[right];
				
				//从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
				while (left < right && list[left] <= baseNum)
					left = left + 1;
				
				
				//最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
				list[right] = list[left];
			}
			//最后就是把baseNum放到该left的位置
			list[left] = baseNum;
			
			//最终，我们发现left位置的左侧数值部分比left小，left位置右侧数值比left大
			//至此，我们完成了第一篇排序
			return left;
		}
		
		//递减
		private function DivisionDescrease(list:Array, left:int , right:int ):int
		{
			//首先挑选一个基准元素
			var baseNum:int = list[left];
			
			while (left < right)
			{
				//从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
				while (left < right && list[right] <= baseNum)
					right = right - 1;
				
				//最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
				list[left] = list[right];
				
				//从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
				while (left < right && list[left] >= baseNum)
					left = left + 1;
				
				
				//最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
				list[right] = list[left];
			}
			//最后就是把baseNum放到该left的位置
			list[left] = baseNum;
			
			//最终，我们发现left位置的左侧数值部分比left小，left位置右侧数值比left大
			//至此，我们完成了第一篇排序
			return left;
		}
		/**
		 *	c++ 内默认的 快速排序逻辑 
		 * 	可对数组内的一个连续的范围进行排序
		 * @param list		待排序的数组
		 * @param left		排序范围的左边界
		 * @param right		排序范围的右边界
		 * 
		 * var quickSort:QuickSortClass = new QuickSortClass();
			var arr:Array = [2,3322,421,1412,41424,142,124,233,242421,2423,42,241,1414,14,14,14141,12,4,35436,5654,646546,4564567,22];
			quickSort.QuickSort(arr, 0, arr.length -1, false);
			
			var t:int = getTimer();
			trace(arr);
			trace("耗时：", getTimer() - t); //耗时： 0
		 */		
		public function QuickSort(list:Array, left:int, right:int, isIncrease:Boolean = true):void
		{
			//左下标一定小于右下标，否则就超越了
			if (left < right)
			{
				//对数组进行分割，取出下次分割的基准标号
				var i:int;
				if (isIncrease)
				{
					i = DivisionIncrease(list, left, right);
				}else
				{
					i = DivisionDescrease(list, left, right);
				}
				
				//对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
				QuickSort(list, left, i - 1, isIncrease);
				
				//对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
				QuickSort(list, i + 1, right, isIncrease);
			}
		}
	}
}